package com.jinxi.algorithm;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @Autho changqi.wu
 * @Date 路在脚下，使劲踩！
 */
public class BinTree {

    private static TreeNode init(){

        TreeNode node1 = new TreeNode(3);
        TreeNode node2 = new TreeNode(5);
        TreeNode node3 = new TreeNode(1);

        TreeNode node4 = new TreeNode(6);
        TreeNode node5 = new TreeNode(2);
        TreeNode node6 = new TreeNode(0);
        TreeNode node7 = new TreeNode(8);
        TreeNode node8 = new TreeNode(7);
        TreeNode node9 = new TreeNode(4);

        node1.left = node2;
        node1.right = node3;

        node2.left = node4;
        node2.right = node5;

        node3.left = node6;
        node3.right = node7;

        node3.left = node6;
        node3.right = node7;

        node5.left = node8;
        node5.right = node9;

        return  node1;
    }

    public static void main(String[] args) {
        TreeNode root = init();
//        traverse(root);

        TreeNode p = new TreeNode(5);
        TreeNode q = new TreeNode(1);

        TreeNode fa = lowestCommonAncestor(root, p, q);
        System.out.println(fa.value);
    }

    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        List<TreeNode> foot1 = new ArrayList();
        traverse(root, p, foot1);
        List<TreeNode> foot2 = new ArrayList();
        traverse(root, q, foot2);
        int size = foot1.size() > foot2.size() ? foot2.size() : foot1.size();
        boolean find = false;
        for (int i = 0; i < size; i++) {
            TreeNode node1 = foot1.get(i);
            TreeNode node2 = foot2.get(i);
            if (node1.value != node2.value) {
                find = true;
                return foot1.get(i - 1);
            }
        }
        if(!find){
            return foot1.get(size - 2);
        }
        return null;
    }

    public static void traverse(TreeNode root,TreeNode end, List<TreeNode> foot){
        LinkedList<TreeNode> list= new LinkedList<>();
        list.add(root);
        TreeNode current;
        while (!list.isEmpty()) {
            current = list.poll();
            foot.add(current);
//            System.out.println(current.value);
            if(current.value == end.value){
                return;
            }
            if(current.left != null){
                list.add(current.left);
            }
            if(current.right != null){
                list.add(current.right);
            }
        }
    }


    public static void traverse(TreeNode root){
        if(root == null){
            return;
        }
        LinkedList<TreeNode> list= new LinkedList<>();
        list.add(root);
        TreeNode current;
        while (!list.isEmpty()) {
            current = list.poll();
            System.out.println(current.value);
            if(current.left != null){
                list.add(current.left);
            }
            if(current.right != null){
                list.add(current.right);
            }
        }
    }

    static class TreeNode//节点结构
    {
        int value;
        TreeNode left;
        TreeNode right;

        TreeNode(int value)
        {
            this.value = value;
        }
    }
}
